package tree;


public class SegementTree<E>  {

    private E[] tree;   //将data转换成线段树后，用来承载线段树的所有节点

    private E[] data;

    private Merger<E> merger;

    public SegementTree(E[] arr,Merger<E> merger){
        this.data = (E[]) new Object[arr.length];
        this.merger = merger;
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }

        //为线段树分配空间
        tree = (E[]) new Object[4*arr.length];
        buildSegmentTree(0,0,data.length-1);
    }

    public E get(int index){
        if(index < 0 || index > data.length){
            throw new IllegalArgumentException("index is illegal");
        }

        return data[index];
    }


    public int getSize(){
        return data.length;
    }

    //获取给定索引的左孩子的索引
    private int leftChild(int index){
        return 2*index + 1 ;
    }

    //获取给定索引的右孩子的索引
    private int rightChild(int index){
        return 2 * index + 2;
    }

    /**
     * 在 treeIndex 的位置创建区间 [l...right]
     * @param treeIndex: 线段树根节点所在索引
     * @param l：左区间
     * @param r：右区间
     */
    public void buildSegmentTree(int treeIndex,int l,int r){

        if( l == r){
            tree[treeIndex] = data[l];
            return;
        }

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        //左右子树存储的区间
        int mid = l + (r - l) / 2;  //左区间 + 左右区间的差，防止整型溢出

        buildSegmentTree(leftTreeIndex,l,mid);
        buildSegmentTree(rightTreeIndex,mid+1 , r );

        //当前节点的值
        tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);

    }

    /**
     * 查询线段树
     * @param queryL：左区间
     * @param queryR：右区间
     * @return
     */
    public E query(int queryL,int queryR){
        //边界检查
        return query(0,0,data.length-1,queryL,queryR);
    }

    /**
     * 在以 treeIndex为根的线段树中[l..r]的范围里，搜索区间[ queryL ... queryR ]的值
     * @param treeIndex：根节点索引
     * @param l：当前线段树的左区间
     * @param r：当前线段树的右区间
     * @param queryL：查询范围的左区间
     * @param queryR：查询范围的右区间
     * @return
     */
    private E query(int treeIndex,int l , int r, int queryL,int queryR){

        if(l == queryL && r == queryR){
            return tree[treeIndex];
        }

        int mid = l +(r-l)/2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        if(queryL > mid+1){
            return query(rightTreeIndex,mid+1,r,queryL,queryR);
        }else if(queryR <= mid) {
            return query(leftTreeIndex,l,mid,queryL,queryR);
        }


        //用户查询的区间不在一个线段树区间内
        E leftResult = query(leftTreeIndex,l,mid,queryL,mid);
        E rightResult = query(rightTreeIndex,mid+1,r,mid+1,queryR);
        return merger.merge(leftResult,rightResult);

    }


    public void set(int index,E e){
        //index合法性判断

        data[index] = e;
        //更新tree
        set(0, 0, data.length-1, index, e);
    }

    // 在以treeIndex为根的线段树中更新index值为e
    private void set(int treeIndex,int l,int r,int index,E e){
        if(l == r){
            //l == r 表示找到已更新的节点
            tree[treeIndex] = e;
            return;
        }

        int mid = l + (r-l)/2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if(index >= mid+1){
            //在右子树中找
            set(rightTreeIndex, mid+1 , r , index , e);
        }else {
            set(leftTreeIndex, l , mid , index ,e);
        }

        //在对节点更新的同时，也必须要维护父区间的值
        tree[treeIndex] = merger.merge( tree[leftTreeIndex] , tree[rightTreeIndex] );
    }

}
